package com.leetcode.algorithm.y22.m07;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;

/**
 * 200. 岛屿数量
 * 
 * https://leetcode.cn/problems/number-of-islands/
 * 
 * @author jie.deng
 *
 */
class Question0200Solution01 {
	
	public int numIslands(int[][] grid) {
		int rows = grid.length;
		int cols = grid[0].length;
		int cnt = 0;

		Set<Integer> visitedSet = new HashSet<>();
		Queue<int[]> queue = new LinkedList<>();
		for (int i = 0; i < rows; i++) {
			for (int j = 0; j < cols; j++) {
				if (grid[i][j] == '1' && visitedSet.add(getIdx(i, j, cols))) {
					cnt++;
					int idx = getIdx(i, j, cols);
					queue.offer(new int[] { i, j });
					while (!queue.isEmpty()) {
						int[] arr = queue.poll();
						int row = arr[0];
						int col = arr[1];
						// 上
						if (row >= 1) {
							idx = getIdx(row - 1, col, cols);
							if (grid[row - 1][col] == '1' && visitedSet.add(idx)) {
								queue.offer(new int[] { row - 1, col });
							}
						}
						// 下
						if (row < rows - 1) {
							idx = getIdx(row + 1, col, cols);
							if (grid[row + 1][col] == '1' && visitedSet.add(idx)) {
								queue.offer(new int[] { row + 1, col });
							}
						}
						// 左
						if (col >= 1) {
							idx = getIdx(row, col - 1, cols);
							if (grid[row][col - 1] == '1' && visitedSet.add(idx)) {
								queue.offer(new int[] { row, col - 1 });
							}
						}
						// 下
						if (col < cols - 1) {
							idx = getIdx(row, col + 1, cols);
							if (grid[row][col + 1] == '1' && visitedSet.add(idx)) {
								queue.offer(new int[] { row, col + 1 });
							}
						}
					}
				}
			}
		}
		return cnt;
	}

	private int getIdx(int row, int col, int cols) {
		return row * cols + col;
	}    
}